package Hot_100;

import org.junit.Test;

import java.util.*;

public class T49_groupAnagrams {
    @Test
    public void test() {
        String []str={"eat", "tea", "tan", "ate", "nat", "bat"};
//        System.out.println(groupAnagrams_1(str));
        System.out.println(groupAnagrams_2(str));

//        System.out.println((char)('a' + 2));

    }


//    法一:排序，字母相同但排列不同的串，排序之后是相同的
    public List<List<String>> groupAnagrams_1(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }

        HashMap<String, ArrayList<String>> map = new HashMap<>();    // key:排序后的串    未排序但字母相同的串
        List<List<String>> ans = new ArrayList<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            Arrays.sort(charArray);

            String s = String.valueOf(charArray);
//            System.out.println(s);    s是排序
//            System.out.println(str);  str是未排序

            if (!map.containsKey(s)) {
                map.put(s, new ArrayList<String>());
            }
            List<String> value = map.get(s);
            value.add(str);
        }

//        for (ArrayList<String> value: map.values()) {
//            ans.add(value);
//        }
        return new ArrayList(map.values());
    }

//    法二 对于字母相同但排列不同的串，其中串包含的字符个数是相同，因此可以生成一个eg: a1b2c3... 作为key，而value是字母相同但排列不同的串
    public List<List<String>> groupAnagrams_2(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }

        HashMap<String, ArrayList<String>> map = new HashMap<>();

        for (String str : strs) {
            int[] count = new int[26];  //记录串中字母出现的个数

            for (int i = 0; i < str.length(); i++) {
                count[str.charAt(i) - 'a']++;
            }

            StringBuffer key = new StringBuffer();
            for (int i = 0; i < count.length; i++) {
                key.append((char)('a' + i));
                key.append(count[i]);
            }

            String relKey = key.toString();

            if (!map.containsKey(relKey)) {
                map.put(relKey, new ArrayList<>());
            }
            ArrayList<String> val = map.get(relKey);
            val.add(str);
        }



        return new ArrayList<>(map.values());  //map.values()返回的类型是 Collection<V>,需要强转为ArrayList
    }

}
